#ifndef BT_HASH_MAP_H
#define BT_HASH_MAP_H

#include "btAlignedObjectArray.h"

const int BT_HASH_NULL=0xffffffff;

template <class Value>
class btHashKey
{
    int    m_uid;
public:

    btHashKey(int uid)
        :m_uid(uid)
    {
    }

    int    getUid() const
    {
        return m_uid;
    }

    //to our success
    SIMD_FORCE_INLINE    unsigned int getHash()const
    {
        int key = m_uid;
        // Thomas Wang's hash
        key += ~(key << 15);
        key ^=  (key >> 10);
        key +=  (key << 3);
        key ^=  (key >> 6);
        key += ~(key << 11);
        key ^=  (key >> 16);
        return key;
    }

    btHashKey    getKey(const Value& value) const
    {
        return btHashKey(value.getUid());
    }
};


template <class Value>
class btHashKeyPtr
{
    int    m_uid;
public:

    btHashKeyPtr(int uid)
        :m_uid(uid)
    {
    }

    int    getUid() const
    {
        return m_uid;
    }

    //to our success
    SIMD_FORCE_INLINE    unsigned int getHash()const
    {
        int key = m_uid;
        // Thomas Wang's hash
        key += ~(key << 15);
        key ^=  (key >> 10);
        key +=  (key << 3);
        key ^=  (key >> 6);
        key += ~(key << 11);
        key ^=  (key >> 16);
        return key;
    }

    btHashKeyPtr    getKey(const Value& value) const
    {
        return btHashKeyPtr(value->getUid());
    }
};

///The btHashMap template class implements a generic and lightweight hashmap.
///A basic sample of how to use btHashMap is located in Demos\BasicDemo\main.cpp
template <class Key, class Value>
class btHashMap
{

    btAlignedObjectArray<int>        m_hashTable;
    btAlignedObjectArray<int>        m_next;
    btAlignedObjectArray<Value>        m_valueArray;



    void    growTables(const Key& key)
    {
        int newCapacity = m_valueArray.capacity();

        if (m_hashTable.size() < newCapacity)
        {
            //grow hashtable and next table
            int curHashtableSize = m_hashTable.size();

            m_hashTable.resize(newCapacity);
            m_next.resize(newCapacity);

            int i;

            for (i= 0; i < newCapacity; ++i)
            {
                m_hashTable[i] = BT_HASH_NULL;
            }
            for (i = 0; i < newCapacity; ++i)
            {
                m_next[i] = BT_HASH_NULL;
            }

            for(i=0;i<curHashtableSize;i++)
            {
                const Value& value = m_valueArray[i];

                int    hashValue = key.getKey(value).getHash() & (m_valueArray.capacity()-1);    // New hash value with new mask
                m_next[i] = m_hashTable[hashValue];
                m_hashTable[hashValue] = i;
            }


        }
    }

    public:

    void insert(const Key& key, const Value& value) {
        int hash = key.getHash() & (m_valueArray.capacity()-1);
        //don't add it if it is already there
        if (find(key))
        {
            return;
        }
        int count = m_valueArray.size();
        int oldCapacity = m_valueArray.capacity();
        m_valueArray.push_back(value);
        int newCapacity = m_valueArray.capacity();
        if (oldCapacity < newCapacity)
        {
            growTables(key);
            //hash with new capacity
            hash = key.getHash() & (m_valueArray.capacity()-1);
        }
        m_next[count] = m_hashTable[hash];
        m_hashTable[hash] = count;
    }

    void remove(const Key& key) {

        int hash = key.getHash() & (m_valueArray.capacity()-1);

        int pairIndex = findIndex(key);

        if (pairIndex ==BT_HASH_NULL)
        {
            return;
        }

        // Remove the pair from the hash table.
        int index = m_hashTable[hash];
        btAssert(index != BT_HASH_NULL);

        int previous = BT_HASH_NULL;
        while (index != pairIndex)
        {
            previous = index;
            index = m_next[index];
        }

        if (previous != BT_HASH_NULL)
        {
            btAssert(m_next[previous] == pairIndex);
            m_next[previous] = m_next[pairIndex];
        }
        else
        {
            m_hashTable[hash] = m_next[pairIndex];
        }

        // We now move the last pair into spot of the
        // pair being removed. We need to fix the hash
        // table indices to support the move.

        int lastPairIndex = m_valueArray.size() - 1;

        // If the removed pair is the last pair, we are done.
        if (lastPairIndex == pairIndex)
        {
            m_valueArray.pop_back();
            return;
        }

        // Remove the last pair from the hash table.
        const Value* lastValue = &m_valueArray[lastPairIndex];
        int lastHash = key.getKey(*lastValue).getHash() & (m_valueArray.capacity()-1);

        index = m_hashTable[lastHash];
        btAssert(index != BT_HASH_NULL);

        previous = BT_HASH_NULL;
        while (index != lastPairIndex)
        {
            previous = index;
            index = m_next[index];
        }

        if (previous != BT_HASH_NULL)
        {
            btAssert(m_next[previous] == lastPairIndex);
            m_next[previous] = m_next[lastPairIndex];
        }
        else
        {
            m_hashTable[lastHash] = m_next[lastPairIndex];
        }

        // Copy the last pair into the remove pair's spot.
        m_valueArray[pairIndex] = m_valueArray[lastPairIndex];

        // Insert the last pair into the hash table
        m_next[pairIndex] = m_hashTable[lastHash];
        m_hashTable[lastHash] = pairIndex;

        m_valueArray.pop_back();

    }


    int size() const
    {
        return m_valueArray.size();
    }

    const Value* getAtIndex(int index) const
    {
        btAssert(index < m_valueArray.size());

        return &m_valueArray[index];
    }

    Value* getAtIndex(int index)
    {
        btAssert(index < m_valueArray.size());

        return &m_valueArray[index];
    }

    Value* operator[](const Key& key) {
        return find(key);
    }

    const Value*    find(const Key& key) const
    {
        int index = findIndex(key);
        if (index == BT_HASH_NULL)
        {
            return NULL;
        }
        return &m_valueArray[index];
    }

    Value*    find(const Key& key)
    {
        int index = findIndex(key);
        if (index == BT_HASH_NULL)
        {
            return NULL;
        }
        return &m_valueArray[index];
    }


    int    findIndex(const Key& key) const
    {
        int hash = key.getHash() & (m_valueArray.capacity()-1);

        if (hash >= m_hashTable.size())
        {
            return BT_HASH_NULL;
        }

        int index = m_hashTable[hash];
        while ((index != BT_HASH_NULL) && (key.getUid() == key.getKey(m_valueArray[index]).getUid()) == false)
        {
            index = m_next[index];
        }
        return index;
    }

    void    clear()
    {
        m_hashTable.clear();
        m_next.clear();
        m_valueArray.clear();
    }

};

#endif //BT_HASH_MAP_H
